|
|
Konstrukce Grayových kódů se speciálními vlastnostmi
Novotný, Tomáš ; Dvořák, Tomáš (vedoucí práce) ; Fink, Jiří (oponent)
(Cyklický) Grayův kód řádu n je (cyklická) posloupnost všech n- bitových řetězců, v nichž se sousední řetězce liší vždy v jediném bitu. Ruskey a Savage v roce 1993 publikovali otázku, zdali lze každé párování v hyperkrychli rozšířit na cyklický Grayův kód. Problém je stále otevřený, pozitivní řešení je však známo pro každé perfektní párování (Fink, 2007). Hlavním výsledkem práce je zobecnění Finkova výsledku na Grayův kód s předepsanými koncovými vrcholy. Charakterizace takto rozšiřitelných perfektních párování je pro n = 5 ověřena na počítači, tento výsledek slouží jako báze induktivního důkazu tvrzení pro vyšší dimenze. Druhá část práce se soustředí na problém maximálních párování v hy- perkrychlích co nejmenší velikosti, která jsou perspektivním kandidátem na ne- gativní řešení problému Ruskey-Savage. Je zde navržena nová metoda, která dává především pro malé dimenze párování menší velikosti nežli klasická asymptoticky optimální konstrukce (Forcade, 1973). Upravený program z první části je následně využit k testování problému Ruskey-Savage pro tato párování, rozšiřující Grayův kód je však vždy nalezen. 1
|
host ::
RSS.